"""
KMP 算法思想归纳如下：将主串T的第一个字符与模式串P的第一个字符进行匹配。
    如果相等，则依次比较T和P的下一个字符。
    如果不相等，则主串T移动(已匹配字符数-对应的部分匹配值)位，继续匹配。
    关于移动位数的解释：已匹配字符数，即当前已完成匹配的字符数量。
    部分匹配值就是前缀和后缀的最长的共有元素的长度。
    前缀指除了最后一个字符以外，一个字符串的全部头部组合。
    后缀指除了第一个字符以外，一个字符串的全部尾部组合。
    请根据 KMP 算法原理，编写 kmp 算法实现字符匹配吧。
    主串:123456456
    目标串:123456
"""


def part_match(string):
    n = len(string)
    failure = [-1] * n
    for i in range(n):
        substring = string[: i + 1]
        for j in range(i):
            if substring[: j + 1] == substring[-j - 1 :]:
                failure[i] = j
    return failure


def kmp(string, pattern):
    failure = part_match(pattern)
    n = len(string)
    m = len(pattern)
    i, j = 0, 0
    while i < n and j < m:
        if string[i] == pattern[j]:
            i += 1
            j += 1
        elif j > 0:
            j = failure[j - 1] + 1
        else:
            i += 1
    if j == m:
        return i - m
    else:
        return None


string = "123456456"
pattern = "123456"
answer = string.index(pattern)
solution = kmp(string, pattern)
print(answer == solution)
